Bowling

Memory limit: 256 MB

Byteasar is a fan of both bowling and statistics. He has written down the results of a few past bowling games. Unfortunately, some characters in the notes are blurry, and thus unreadable. Byteasar asks you to write a program to calculate the number of distinct games which are consistent with his notes.

Rules of Bowling

A bowling game consists of frames: simple frames and one final frame. In a typical game . At the beginning of each frame 10 pins are put standing upright at the end of a lane and a player gets no more than two (or three for the final frame) attempts (shots) to throw a bowling ball down the lane to try to knock down as many pins as possible. Each frame is denoted by two (for a simple frame) or three (for the final frame) characters.

For each shot the player receives as basic points the total number of pins knocked down in this shot. The player's basic points in each frame are the sum of basic points of all the shots in this frame. If all 10 pins are knocked down in a simple frame (and therefore 10 basic points are earned), the player gets additional bonus points.

For a simple frame the rules are the following:

• If a player knocks down all 10 pins in the first shot of a frame, she gets a strike and the frame ends. As bonus points she gets the sum of basic points of her next two shots. A strike is denoted as "x-".
• If a player knocks down all 10 pins using both shots of a frame, she gets a spare. As bonus points she gets the basic points of her next shot. A spare is denoted as "/", where is a digit describing the number of pins knocked down in the first shot of the frame.
• If 9 or fewer pins are knocked down after both shots, the player gets just basic points and such a frame is denoted as "", where is the one-digit number of pins knocked down in the first shot, and is the one-digit number of pins knocked down in the second shot ().

Note that bonus points are included to the score of a frame in which the strike or the spare was obtained, regardless of the fact that the exact number of bonus points depends on future shots in next frames.

For the final frame the rules are the following:

• Initially the player receives two shots in this frame. If 9 or fewer pins are knocked down in the two shots, the frame ends. Otherwise (if the first two shots are a spare or the first shot is a strike), the player receives a third shot in the frame. Whenever the player knocks down all the pins in any of the three shots, the pins are reset to the initial configuration for the next shot. The score of the final frame is the total number of pins knocked down (note that no bonus points are earned due to strikes and spares).
• Overall there are seven possible configurations of the final frame with the following outcomes ( and stand for one-digit numbers):

  Denotation	Description	Frame Score
  "xxx"	three consecutive strikes	30
  "xx"	two consecutive strikes and a shot with pins knocked down	20 +
  "x/"	a strike and a spare with pins knocked down on its first shot	20
  "x"	a strike and two following shots with and pins knocked down respectively ()	10 + +
  "/x"	a spare with pins knocked down on the first shot and a strike	20
  "/"	a spare with pins knocked down on the first shot and pins knocked down in the last shot	10 +
  "-"	two shots with and pins knocked down respectively ()

Each game is described as a sequence of characters. At the end of the game the total number of points after each frame may be calculated. For example, for a game of frames described as "08x-7/2/x-x-23441/0/x", the player's points after respective frames were as follows:

Frame	Denotation	Basic Points	Bonus Points	Frame Score	Total
1	"08"		-	8	8
2	"x-"			20	28
3	"7/"			12	40
4	"2/"			20	60
5	"x-"			22	82
6	"x-"			15	97
7	"23"		-	5	102
8	"44"		-	8	110
9	"1/"			10	120
final	"0/x"		-	20	140

Input

The first line of input contains one integer (), specifying the number of test cases to consider. The following lines of input contain descriptions of test cases. Each test case is described by three lines of input.

The first line of a test case description contains one integer (), specifying the number of frames. The second line contains a sequence of characters which denotes the game description from Byteasar's notes. Blurry characters are replaced by "?" characters. The third line contains integers, the total number of points after each frame, separated by spaces. In each number either all digits are readable, or all digits are blurry. Numbers in which all digits are blurry are replaced by "-1".

Output

Your program should output lines, one line per each test case in the same order as in the input.

For each test case your program should write one integer: the number of possible distinct games corresponding to the test case. Two games are considered different if and only if they differ in at least one shot, that is, their -character game descriptions are different. You can assume that there is at least one game consistent with each test case in the input. You can assume that the result fits into 64-bit signed integer type.

Example

For the input data:

2
10
08x-7/2/x?x-23??1/???
8 -1 40 60 82 97 102 110 120 140
5
x-x-23?/00-
22 37 42 52 52

the correct result is:

9
10

Explanation to the example: In the first case, in frame 5 after the character "x" the only possible character is "-". In frame 8 the player got 8 points in total. Thus there are 9 possibilities how this sum could have been obtained: . There were no bonus points in frame 9. Therefore, there were no points on the first shot of the final frame. To obtain 20 points in the last two shots, the only possibility is a spare with a following strike in the last shot of the frame. Therefore there are 9 different valid games which correspond to this input data.

In the second case, any character from 0 to 9 is consistent with the input data.

Grading

Subtask	Conditions (in each test case)	Points
1	at most six "?" characters in the input sequence	16
2	the result is at most	17
3	no game whose description contains any characters "x" or "/" is consistent with the input data	26
4	the input sequence ends with "00-" (that is, the player obtained 0 points in the last frame) and last frame scores provided in the third line of input data are all "-1"	23
5	no additional constraints	18